package com.hanxiaozhang.no3algorithm;

import java.util.Stack;

/**
 * 〈一句话功能简述〉<br>
 * 〈在有序数组中，给定一个区间范围，找出该区间的元素个数〉
 * <p>
 * 例如：{1,3,5,8,10,12} 区间[3,10] 个数 4
 *
 * 拓展题：
 * 给定一个非常长的数组，再给你一个区间及值，找到这个区间里有几个这个值。
 * 例如：数组：{0,12,10,9,8,12,5,12,19,8,12,8}
 *  区间及值 {0,5} 12  输出 2
 *  区间及值 {0,8} 12  输出 3
 *
 * @author hanxinghua
 * @create 2023/12/9
 * @since 1.0.0
 */
public class No13SortArrayQueryRange {


    public static void main(String[] args) {

        int[] nums = {1, 3, 5, 8, 10, 12};
        int[] queryRange = {3, 10};

        int result = method2(nums, queryRange);
        System.out.println(result);

        // 拓展题：
        // 给定一个非常长的数组，再给你一个区间及值，找到这个区间里有几个这个值。
        //  数组：{0,12,10,9,8,12,5,12,19,8,12,8}
        //  区间及值 {0,5} 12  输出 2
        //  区间及值 {0,8} 12  输出 3
        // 思路：数据量大，数据分组查找 开始位置 结束位置 ，然后再找有多少个值
        //  找开始位置和结束位置思路：
        //   情况1: 开始位置 在组内，从后边分组找 结束位置
        //   情况2: 结束位置 在组内，从前边分组找 开始位置
        //   情况3: 开始位置 结束位置 都在同组 ，并且 开始位置 < 结束位置，数据在该分组
        //   情况4: 开始位置 结束位置 都在同组 ，并且 开始位置 > 结束位置，分别处理 情况1 和情况2


    }


    /**
     * 二分查找法
     *
     * 时间复杂度 longN ？
     *
     * @param nums
     * @param queryRange
     * @return
     */
    private static int method2(int[] nums, int[] queryRange) {

        int result = 0;
        boolean flag = true;
        // 注意 right=nums.length-1
        int left = 0, right = nums.length - 1, mid = 0,
                compare = queryRange[0], startIndex = 0, endIndex = 0;

        // 注意 left<right
        while (left <= right) {
            mid = (left + right) / 2;
            if (nums[mid] == compare) {
                if (flag) {
                    startIndex = mid;
                    compare = queryRange[1];
                    left = mid + 1;
                    right = nums.length - 1;
                    flag = false;
                } else {
                    endIndex = mid;
                    break;
                }
            } else if (nums[mid] > compare) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        // 开始范围没有值，返回-1
        if (flag) {
            return -1;
        }
        // 结束范围没有值，返回-1
        return endIndex != 0 ? endIndex - startIndex + 1 : -1;
    }


    /**
     * 笨方法
     * <p>
     * 时间复杂度 n
     *
     * @param nums
     * @param queryRange
     */
    private static int method1(int[] nums, int[] queryRange) {
        int result = 0;

        boolean flag = false;
        for (int i = 0; i < nums.length; i++) {

            if (nums[i] == queryRange[0]) {
                flag = true;
            }
            if (flag) {
                result++;
            }
            // 注意边界值
            if (nums[i] == queryRange[1]) {
                flag = false;
            }
        }
        return result;
    }

}
